#include <vector>
#include <map>

using std::map;
using std::vector;


class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> rst;
        rst.reserve(2);
        map<int,int> m; // 存放遍历过的元素和所在位置
        for(size_t i = 0;i < nums.size(); ++ i)
        {
            // 查找target - nums[i] 是否在map中
            if(m.count(target - nums[i]) != 0)
            {
                // 表示找到了
                rst.push_back(i);
                rst.push_back(m[target-nums[i]]);
                return rst;
            }
            else
            {
                // 表示没找到
                m.insert({nums[i],i});
            }
        }
        return rst;
    }
};
